Introduction

Semantic and CPA-Security only provide protection against passive adversaries who can observe but cannot directly interfere with the communication between Alice and Bob. However, oftentimes an attacker Mallory can actually inject traffic between the two legitimate parties.

Consider the scenario where Alice encrypts a message $m$ and sends the resulting ciphertext $c$ to Bob. Mallory can tamper with the communication channel and so she can intercept $c$ and modify it into some other ciphertext $c^{'}$ . Bob will then decrypt $c^{'}$ to a different message $m^{'}$ . Whilst Mallory does not know exactly what $m^{'}$ is, she might be able to obtain some information about it from the way Bob behaves after receiving it. For example, Bob might be expecting a message in a very specific format and if the message he receives is not formatted correctly, he might take significantly longer to respond. Abusing this, Mallory will know if $c^{'}$ decrypts to a correctly formatted message or not.

Example

A more practical and grave example are padding oracle attacks which allow an attacker to completely break the security of CBC encryption and only require a way to know if a ciphertext decrypts to a valid message.

Essentially, a chosen ciphertext attack allows an adversary to force a legitimate party to decrypt arbitrary ciphertexts and to subsequently obtain certain information about the plaintext these ciphertexts decrypt to.

Chosen Ciphertext Attack (CCA)

It is very difficult to actually describe what information the adversary might be able to obtain about the decrypted messages and so this threat model assumes the worst case scenario - it assumes that Mallory is actually able to see the entire message $m^{'}$ which $c^{'}$ decrypts to.

The CCA threat model builds on CPA. In particular, Mallory can query both $Enc_{k}$ and $Dec_{k}$ and her goal is to obtain information about a message $m$ which is the decryption of a particular ciphertext $c$ without directly being able to query $Dec_{k} (c)$ . Notice, however, that since CCA builds on CPA, Mallory is allowed to query $Enc_{k}$ which again means that any cipher which hopes to be CCA-secure must have a non-deterministic encryption function $Enc_{k}$ .

CCA-Security

With the description of the CCA-model, we can now give a definition of what it means for a cipher to be secure under it.

Definition: CCA-Security

The adversary Mallory is allowed to make two types of queries:

Encryption query - Mallory can query $Enc_{k}$ with $q$ messages $m_{1}, m_{2}, ..., m_{q}$ in order to obtain their corresponding ciphertexts $c_{1}, c_{2}, ..., c_{q}$ .
Decryption query - Mallory can also query $Dec_{k}$ with $q^{'}$ ciphertexts $c_{1}^{'}, c_{2}^{'}, ..., c_{q^{'}}^{'}$ in order to obtain their decryptions $m_{1}^{'}, m_{2}^{'}, ..., m_{q^{'}}^{'}$ .

Finally, Mallory chooses two messages $m_{a}, m_{b}$ , which can be one of $m_{1}, m_{2}, ..., m_{q}$ or $m_{1}^{'}, m_{2}^{'}, ..., m_{q^{'}}^{'}$ , and is then presented with a ciphertext $c$ which is either the encryption of $m_{a}$ or $m_{b}$ . Her goal is to determine whether $c$ belongs to $m_{a}$ or $m_{b}$ , but she is not allowed to directly query $Dec_{k} (c)$ .

The cipher $(Enc, Dec)$ is CCA-secure, if for all keys $k \in K$ , Mallory cannot guess with probability better than $\frac{1}{2} + negl (n)$ whether $c$ is the encryption of $m_{a}$ , or $m_{b}$ , i.e.

$k \leftarrow_{R} K, m \leftarrow_{R} {m_{a}, m_{b}} Pr [Mallory (Enc_{k} (m)) = m] \leq \frac{1}{2} + negl (n)$

Definition Breakdown

As with CPA, Mallory is allowed to query $Enc_{k}$ with messages $m_{1}, m_{2}, ..., m_{q}$ of her choice. She is additionally allowed to query $Dec_{k}$ with ciphertexts $c_{1}, c_{2}, ..., c_{q}$ of her choice. Mallory is also allowed to pick the messages $m_{a}$ and $m_{b}$ herself and they can even be two of the previously queried messages or two of the decryptions of the queried ciphertexts, or both. She is then given a ciphertext $c$ and has to determine if it is an encryption of $m_{a}$ or $m_{b}$ . The only restriction is that Mallory cannot directly query $Dec_{k}$ with $c$ , for otherwise no cipher would ever satisfy the definition.

A cipher is CCA-secure if no matter what Mallory does, she cannot determine whether $c$ is the encryption of $m_{a}$ or $m_{b}$ with probability significantly better than $\frac{1}{2}$ .

Since CCA-security builds on top of CPA-security, it is a stronger notion of secrecy. In particular, every CCA-secure cipher is also CPA-secure, but the other way around is not necessarily true.

Theoretical Implementation

Although there are ciphers which provide CCA-security, they are not used in practice because they provide no benefit in either security or efficiency over ciphers which satisfy the even stronger notion of index.

The Cyberclopaedia

Introduction

Chosen Ciphertext Attack (CCA)

CCA-Security

Theoretical Implementation